﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Collections;
using System.Diagnostics;

namespace Qreed.Drawing.Drawing2D
{
    [Serializable]
    public class Polygon2D : LineSegment2D
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="Polygon2D"/> class.
        /// </summary>
        /// <param name="copyFrom">The copy from buffer.</param>
        /// <param name="startIndex">The start index.</param>
        /// <param name="length">The length.</param>
        public Polygon2D(PointF[] copyFrom, int startIndex, int length) : base(copyFrom, startIndex, length)
        {
            
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="ClosedLineSegment2D"/> class.
        /// </summary>
        /// <param name="vertices">The vertices.</param>
        public Polygon2D(PointF[] vertices) : base(vertices)
        {
            
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Polygon2D"/> class.
        /// </summary>
        public Polygon2D() : base()
        {
            Vertices.OnChange += new EventHandler<Qreed.Collections.NotifyOnChangeEventArgs<PointF>>(Vertices_OnChange);
        }

        void Vertices_OnChange(object sender, Qreed.Collections.NotifyOnChangeEventArgs<PointF> e)
        {
            _exteriorSides = null;
        }

        /// <summary>
        /// Validates this instance.
        /// </summary>
        public void Validate()
        {
            if (Count < 3)
                throw (new ApplicationException("Need at least 3 vertices to form a polygon."));

            for (int i = 0; i < Count; i++)
            {
                Line2D edge = new Line2D(this[i], this[i + 1]);

                PointF? point = GetIntersectionPoint(edge, false);

                if (point.HasValue)
                    throw (new ApplicationException("Only simple polygons are supported."));
            }
        }        

        /// <summary>
        /// Substracts the specified polygon.
        /// </summary>
        /// <param name="polygon">The polygon.</param>
        public void Substract(Polygon2D polygon)
        {
            if (IsInside(polygon))
            {
                if (polygon.WindingOrder == WindingOrder.CounterClockWise)
                    polygon.WindingOrder = WindingOrder.ClockWise;

                // Locate the vertex that is closest to to one of the vertices of the given polygon

                float length = 0.0f;
                int[] indices = GetClosestEdgeIndex(polygon, ref length);

                // Merge the list of vertices by adding a line that connects both polygons

                Vertices.Add(new PointF()); // Add a dummy vertice to the end of the list which we remove later on

                // Duplicate the points that will start the connection so they close it too

                int insertAt = indices[0] + 1;

                Vertices.Insert(insertAt++, polygon[indices[1]]);
                Vertices.Insert(insertAt, Vertices[indices[0]]);

                for (int j = 0; j < polygon.Count; j++)
                {
                    int getAt = indices[1] + j;
                    PointF pt = polygon[getAt];

                    Vertices.Insert(insertAt, pt); // Note: this will change the winding order of the hole polygon
                }

                Vertices.RemoveAt(Vertices.Count - 1); // Remove the dummy vertice
            }
        }

        /// <summary>
        /// Gets the indices of the closest edge between this and the specified polygon.
        /// </summary>
        /// <param name="polygon">The polygon.</param>
        /// <param name="length">The length between the points.</param>
        /// <returns>An array with two indices. The first contains the index of this instance.</returns>
        public int[] GetClosestEdgeIndex(Polygon2D polygon, ref float length)
        {
            int[] bestIndex = { 0, 0 };
            float bestLength = float.MaxValue;

            for (int i = 0; i < polygon.Count; i++)
            {
                PointF pt = polygon[i];
                float currentLength = 0.0f;

                int currentIndex = GetClosestEdgeIndex(pt, ref currentLength);

                if (currentLength <= bestLength)
                {
                    bestIndex[0] = currentIndex;
                    bestIndex[1] = i;
                    bestLength = currentLength;
                }
            }

            length = bestLength;

            return bestIndex;
        }

        /// <summary>
        /// Gets the index of the closest vertex on the edge to the given point.
        /// </summary>
        /// <param name="pt">The point to check.</param>
        /// <param name="length">The length between the edge and the given point.</param>
        /// <returns>The index of the vertex.</returns>
        public int GetClosestEdgeIndex(PointF pt, ref float length)
        {
            int bestIndex = 0;
            float bestLength = float.MaxValue;

            for (int i = 0; i < Count; i++)
            {
                PointF edgePoint = this[i];

                float currentLength = GetVectorLength(pt, edgePoint);

                if (currentLength <= bestLength)
                {
                    bestIndex = i;
                    bestLength = currentLength;
                }
            }

            length = bestLength;

            return bestIndex;
        }

        /// <summary>
        /// Gets the length of the vector.
        /// </summary>
        /// <param name="ptA">The pt A.</param>
        /// <param name="ptB">The pt B.</param>
        /// <returns></returns>
        internal static float GetVectorLength(PointF ptA, PointF ptB)
        {
            PointF v = new PointF(ptB.X - ptA.X, ptB.Y - ptA.Y);
            float length = (float)Math.Sqrt((double)(v.X * v.X + v.Y * v.Y));
            return length;
        }

        /// <summary>
        /// Determines whether the specified inner polygon is inside.
        /// </summary>
        /// <param name="innerPolygon">The inner polygon.</param>
        /// <returns>
        /// 	<c>true</c> if the specified inner polygon is inside; otherwise, <c>false</c>.
        /// </returns>
        public bool IsInside(Polygon2D innerPolygon)
        {
            foreach (PointF pt in innerPolygon.Vertices)
            {
                if (!IsInside(pt))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Determines whether the polygon contains the specified pt.
        /// </summary>
        /// <param name="pt">The point to check.</param>
        /// <returns>
        /// 	<c>true</c> if the polygon contains the specified point; otherwise, <c>false</c>.
        /// </returns>
        /// <remarks>
        /// http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
        /// </remarks>
        public bool IsInside(PointF pt)
        {
            bool c = false;

            int i, j;

            for (i = 0, j = Count - 1; i < this.Count; j = i++)
            {
                float vertx_i = this.Vertices[i].X;
                float verty_i = this.Vertices[i].Y;
                float vertx_j = this.Vertices[j].X;
                float verty_j = this.Vertices[j].Y;

                if (((verty_i > pt.Y) != (verty_j > pt.Y)) &&
                    (pt.X < (vertx_j - vertx_i) * (pt.Y - verty_i) / (verty_j - verty_i) + vertx_i))
                {
                    c = !c;
                }
            }

            return c;
        }

        /// <summary>
        /// Triangulates this instance.
        /// </summary>
        /// <returns>A list of triangles.</returns>
        public IList<Polygon2D> Triangulate()
        {
            List<Polygon2D> triangles = new List<Polygon2D>();

            if (Vertices.Count == 3)
            {
                triangles.Add(this);
            }
            else if (SegmentType == SegmentType.Convex && false)
            {
                PointF p1 = Vertices[0];

                for (int i = 1; i < Count - 1; i++)
                {
                    PointF p2 = Vertices[i];
                    PointF p3 = Vertices[i + 1];

                    Polygon2D triangle = new Polygon2D(new PointF[] { p1, p2, p3 });
                    triangles.Add(triangle);
                }
            }
            else
            {
                Polygon2D polygon = new Polygon2D(Vertices.ToArray());

                for (int i = 0; i < Vertices.Count; i++)
                {
                    Debug.WriteLine(string.Format("{0:000} {1} {2} {3}", i, IsEar(i), GetCrossProduct(i), Vertices[i])); 
                }

                //triangles.Add(this);

                //return triangles;

                int lastCount = polygon.Vertices.Count;

                while (polygon.Vertices.Count > 3)
                {
                    Polygon2D triangle = polygon.CutEar();

                    if (triangle == null || lastCount == polygon.Vertices.Count)
                    {
                        Debug.WriteLine("Warning ... adding invalid polygon!!");
                        //triangles.Add(polygon);
                        break;
                    }

                    triangles.Add(triangle);
                    lastCount = polygon.Vertices.Count;
                }

                triangles.Add(polygon);
            }

            return triangles;
        }

        private Polygon2D CutEar()
        {
            for (int i = 0; i < Vertices.Count; i++)
            {
                if (IsEar(i))
                {
                    PointF[] points = new PointF[] { this[i - 1], this[i], this[i + 1] };
                    Polygon2D triangle = new Polygon2D(points);

                    Vertices.RemoveAt(i);

                    return triangle;
                }
            }

            return null;
        }

        private bool IsEar(int pointIndex)
        {
            if (GetCrossProduct(pointIndex) < 0.0f) // Turns to the right
            {
                /*Polygon2D testPolygon = new Polygon2D(new PointF[] { this[pointIndex - 1], this[pointIndex], this[pointIndex + 1] });

                for (int i = 0; i < Vertices.Count; i++)
                {
                    PointF testPoint = this[i];

                    if (testPolygon.Vertices.Contains(testPoint))
                        continue;

                    if (testPolygon.IsInside(testPoint))
                        return false;
                }

                return true;*/

                PointF p0 = this[pointIndex - 1];
                PointF p1 = this[pointIndex + 1];

                Line2D line = new Line2D(p0, p1);

                return GetIntersectionPoint(line, false) == null;
            }
            
            return false;
        }

        private List<LineSegment2D> _exteriorSides;
        /// <summary>
        /// Gets the sides.
        /// </summary>
        /// <value>The sides.</value>
        public LineSegment2D[] ExteriorSides
        {
            get
            {
                if (Count < 3)
                    return null;

                if (_exteriorSides == null)
                    CalculateExteriorSides();

                return _exteriorSides != null ? _exteriorSides.ToArray() : null;
            }
        }

        private void CalculateExteriorSides()
        {
            for (int i = 0; i < Count; i++)
            {
                PointF current = this[i];
                PointF next = this[i + 1];
                
                int[] indices = GetIndicesOf(next);
            }
        }

        private int[] GetIndicesOf(PointF locate)
        {
            List<int> indices = new List<int>();

            for (int i = 0; i < Vertices.Count; i++)
            {
                if (Vertices[i] == locate)
                    indices.Add(i);
            }

            return indices.ToArray();
        }
    }
}
